Dr. Chan, Chun-Hsiang @ Department of Geography,
National Taiwan Normal University, Taipei, Taiwan
# import packages
import numpy as np
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
G = nx.erdos_renyi_graph(50, 0.5, seed=21, directed=False)
options = {
"font_size": 8,
"node_size": 100,
"node_color": "#A0CBE2",
"edge_color": "brown",
"linewidths": 0.1,
"width": 0.08,
}
plt.subplots(figsize=[12,6], dpi=100)
nx.draw_networkx(G, **options, with_labels = True)
ax = plt.gca()
ax.margins(0.001)
plt.axis("off")
plt.show()
# is the graph connected?
nx.is_connected(G)
True
# number of connected component
nx.number_connected_components(G)
1
# the set of nodes in the component of graph containing node n.
np.array(nx.node_connected_component(G, 11))
array({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49},
dtype=object)
# network initialization
DG = nx.fast_gnp_random_graph(100, 0.005, seed=21, directed=True)
options = {
"font_size": 8,
"node_size": 100,
"node_color": "#A0CBE2",
"edge_color": "brown",
"linewidths": 0.1,
"width": 0.08,
}
plt.subplots(figsize=[12,6], dpi=100)
nx.draw_networkx(DG, **options, with_labels = True)
ax = plt.gca()
ax.margins(0.001)
plt.axis("off")
plt.show()
# network initialization
DG1 = nx.gnm_random_graph(20, 40, seed=10, directed=True)
options = {
"font_size": 8,
"node_size": 100,
"node_color": "#A0CBE2",
"edge_color": "brown",
"linewidths": 0.1,
"width": 0.08,
}
plt.subplots(figsize=[12,6], dpi=100)
nx.draw_networkx(DG1, **options, with_labels = True)
ax = plt.gca()
ax.margins(0.001)
plt.axis("off")
plt.show()
# network initialization
DG2 = nx.gnm_random_graph(20, 100, seed=10, directed=True)
options = {
"font_size": 8,
"node_size": 100,
"node_color": "#A0CBE2",
"edge_color": "brown",
"linewidths": 0.1,
"width": 0.08,
}
plt.subplots(figsize=[12,6], dpi=100)
nx.draw_networkx(DG2, **options, with_labels = True)
ax = plt.gca()
ax.margins(0.001)
plt.axis("off")
plt.show()
1) weakly connected - replacing all of G's directed edges with undirected edges produces a connected (undirected) graph.
2) connected - contains a directed path from u to v OR a directed path from v to u for every pair of vertices u, v
3) strongly connected - contains a directed path from u to v AND a directed path from v to u for every pair of vertices u, v
Source: https://math.stackexchange.com/questions/1614641/weak-regular-and-strong-connectivity-in-directed-graphs
# Test directed graph for strong connectivity
nx.is_strongly_connected(DG)
False
# number of strongly connected components in graph
nx.number_strongly_connected_components(DG)
100
# Test directed graph for weak connectivity
nx.is_weakly_connected(DG)
False
# the number of weakly connected components in G
nx.number_weakly_connected_components(DG)
50
Lab Practice:
Please try three random graphs (DG, DG1, and DG2) with and give your observation with explanation.
# your answer:
# network density
nx.density(DG), nx.density(DG1), nx.density(DG2)
(0.005050505050505051, 0.10526315789473684, 0.2631578947368421)
# number of edges in the graph
nx.number_of_edges(DG)
50
# number of nodes in the graph
nx.number_of_nodes(DG)
100
# number of isolates
nx.number_of_isolates(DG)
36
# number of self loop
nx.number_of_selfloops(DG)
0
# average of shortest path length in the network
nx.average_shortest_path_length(DG2)
1.9631578947368422
# diameter of the network
nx.diameter(DG2)
4
# graph initialization
neck = nx.Graph([(0, 1), (0, 2), (1, 2), (2, 3), (3, 4), (4, 5), (3, 5)])
attr_5 = {0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F"}
neck = nx.relabel_nodes(neck, attr_5)
options = {
"font_size": 14,
"node_size": 800,
"node_color": "#A0CBE2",
"edge_color": "skyblue",
"linewidths": 1,
"width": 2,
}
# draw the graph
plt.subplots(figsize=[6,6], dpi=100)
nx.draw_networkx(neck, **options, with_labels = True)
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")
plt.show()
# structure hole: effective size
nx.algorithms.structuralholes.effective_size(neck)
{'A': 1.0,
'B': 1.0,
'C': 2.3333333333333335,
'D': 2.3333333333333335,
'E': 1.0,
'F': 1.0}
# structure hole: constraint
A_neck = nx.adjacency_matrix(neck)
A_neck = np.array(A_neck.todense())
A_neck
array([[0, 1, 1, 0, 0, 0],
[1, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 0],
[0, 0, 1, 0, 1, 1],
[0, 0, 0, 1, 0, 1],
[0, 0, 0, 1, 1, 0]], dtype=int32)
# structure hole: constraint
rowS_neck = np.sum(A_neck, axis=1)
rowS_neck = np.transpose([rowS_neck])
rowS_neck
array([[2],
[2],
[3],
[3],
[2],
[2]], dtype=int32)
# structure hole: constraint
p = A_neck/rowS_neck
p
array([[0. , 0.5 , 0.5 , 0. , 0. ,
0. ],
[0.5 , 0. , 0.5 , 0. , 0. ,
0. ],
[0.33333333, 0.33333333, 0. , 0.33333333, 0. ,
0. ],
[0. , 0. , 0.33333333, 0. , 0.33333333,
0.33333333],
[0. , 0. , 0. , 0.5 , 0. ,
0.5 ],
[0. , 0. , 0. , 0.5 , 0.5 ,
0. ]])
# structure hole: constraint
p*p
array([[0. , 0.25 , 0.25 , 0. , 0. ,
0. ],
[0.25 , 0. , 0.25 , 0. , 0. ,
0. ],
[0.11111111, 0.11111111, 0. , 0.11111111, 0. ,
0. ],
[0. , 0. , 0.11111111, 0. , 0.11111111,
0.11111111],
[0. , 0. , 0. , 0.25 , 0. ,
0.25 ],
[0. , 0. , 0. , 0.25 , 0.25 ,
0. ]])
# structure hole: constraint
cij = (p+p*p)**2
cij
array([[0. , 0.5625 , 0.5625 , 0. , 0. ,
0. ],
[0.5625 , 0. , 0.5625 , 0. , 0. ,
0. ],
[0.19753086, 0.19753086, 0. , 0.19753086, 0. ,
0. ],
[0. , 0. , 0.19753086, 0. , 0.19753086,
0.19753086],
[0. , 0. , 0. , 0.5625 , 0. ,
0.5625 ],
[0. , 0. , 0. , 0.5625 , 0.5625 ,
0. ]])
# structure hole: constraint
np.sum(cij, axis=1)
array([1.125 , 1.125 , 0.59259259, 0.59259259, 1.125 ,
1.125 ])
# structure hole: constraint
# nx.constraint(neck)
nx.algorithms.structuralholes.constraint(neck)
{'A': 1.0069444444444444,
'B': 1.0069444444444444,
'C': 0.6111111111111112,
'D': 0.6111111111111112,
'E': 1.0069444444444444,
'F': 1.0069444444444444}
nx.algorithms.local_constraint(neck, 'A','B'), nx.algorithms.local_constraint(neck, 'A','C')
(0.4444444444444444, 0.5625)
nx.algorithms.local_constraint(neck, 'A','D'), nx.algorithms.local_constraint(neck, 'A','E')
(0.027777777777777776, 0.0)
nx.algorithms.local_constraint(neck, 'A','F')
0.0
0.4444444444444444+0.5625+0.027777777777777776
1.034722222222222
# graph initialization
neck = nx.Graph([(1, 2), (1, 3), (1, 4), (1, 5), (4, 5), (2, 5)])
# attr_5 = {0: "A", 1: "B", 2: "C", 3: "D", 4: "E", 5: "F"}
# neck = nx.relabel_nodes(neck, attr_5)
options = {
"font_size": 14,
"node_size": 800,
"node_color": "#A0CBE2",
"edge_color": "skyblue",
"linewidths": 1,
"width": 2,
}
# draw the graph
plt.subplots(figsize=[6,6], dpi=100)
nx.draw_networkx(neck, **options, with_labels = True)
ax = plt.gca()
ax.margins(0.20)
plt.axis("off")
plt.show()
# structure hole: constraint
A_neck = nx.adjacency_matrix(neck)
A_neck = np.array(A_neck.todense())
A_neck
array([[0, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 0],
[1, 0, 0, 0, 1],
[1, 1, 0, 1, 0]], dtype=int32)
# structure hole: constraint
rowS_neck = np.sum(A_neck, axis=1)
rowS_neck = np.transpose([rowS_neck])
rowS_neck
array([[4],
[2],
[1],
[2],
[3]], dtype=int32)
# structure hole: constraint
p = A_neck/rowS_neck
p
array([[0. , 0.25 , 0.25 , 0.25 , 0.25 ],
[0.5 , 0. , 0. , 0. , 0.5 ],
[1. , 0. , 0. , 0. , 0. ],
[0.5 , 0. , 0. , 0. , 0.5 ],
[0.33333333, 0.33333333, 0. , 0.33333333, 0. ]])
np.matmul(p,p)
array([[0.58333333, 0.08333333, 0. , 0.08333333, 0.25 ],
[0.16666667, 0.29166667, 0.125 , 0.29166667, 0.125 ],
[0. , 0.25 , 0.25 , 0.25 , 0.25 ],
[0.16666667, 0.29166667, 0.125 , 0.29166667, 0.125 ],
[0.33333333, 0.08333333, 0.08333333, 0.08333333, 0.41666667]])
p*p
array([[0. , 0.0625 , 0.0625 , 0.0625 , 0.0625 ],
[0.25 , 0. , 0. , 0. , 0.25 ],
[1. , 0. , 0. , 0. , 0. ],
[0.25 , 0. , 0. , 0. , 0.25 ],
[0.11111111, 0.11111111, 0. , 0.11111111, 0. ]])
# structure hole: constraint
cij = (p+p*p.T)**2
cij
array([[0. , 0.140625 , 0.25 , 0.140625 , 0.11111111],
[0.390625 , 0. , 0. , 0. , 0.44444444],
[1.5625 , 0. , 0. , 0. , 0. ],
[0.390625 , 0. , 0. , 0. , 0.44444444],
[0.17361111, 0.25 , 0. , 0.25 , 0. ]])
# nx.constraint(neck)
nx.algorithms.structuralholes.constraint(neck)
{1: 0.5347222222222222,
2: 0.8350694444444444,
3: 1.0,
4: 0.8350694444444444,
5: 0.7916666666666665}